<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 我们先举例一下 BFS 出现的常见场景好吧，
      // 问题的本质就是让你在一幅「图」中找到从起点start到终点target的最近距离，
      // 这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿。

      // 计算从起点 start 到终点 target 的最近距离
      // int BFS(Node start, Node target) {
      //     Queue<Node> q; // 核心数据结构
      //     Set<Node> visited; // 避免走回头路

      //     q.offer(start); // 将起点加入队列
      //     visited.add(start);
      //     int step = 0; // 记录扩散的步数

      //     while (q not empty) {
      //         int sz = q.size();
      //         /* 将当前队列中的所有节点向四周扩散 */
      //         for (int i = 0; i < sz; i++) {
      //             Node cur = q.poll();
      //             /* 划重点：这里判断是否到达终点 */
      //             if (cur is target)
      //                 return step;
      //             /* 将 cur 的相邻节点加入队列 */
      //             for (Node x : cur.adj())
      //                 if (x not in visited) {
      //                     q.offer(x);
      //                     visited.add(x);
      //                 }
      //         }
      //         /* 划重点：更新步数在这里 */
      //         step++;
      //     }
      // }

      // 力扣111  二叉树的最小深度
      // 显然起点就是root根节点，终点就是最靠近根节点的那个「叶子节点」嘛，叶子节点就是两个子节点都是null的节点：
      var minDepth = function (root) {
        if (root == null) {
          return 0;
        }
        var q = [];
        q.push(root);
        var deep = 1;
        while (q.length > 0) {
          var len = q.length; // 防止加入队列 影响本层的 遍历次数
          for (var i = 0; i < len; i++) {
            var cur = q.shift();
            if (cur.left == null && cur.right == null) {
              return deep;
            }
            if (cur.left != null) {
              q.push(cur.left);
            }
            if (cur.right != null) {
              q.push(cur.right);
            }
            i--;
            len--;
          }
          deep++;
        }
        return deep;
      };

      // 力扣752题 打开转盘锁
      function up(str){
        var res = [];
        for(var i = 0;i<str.length;i++){
          var temp = str.split('')
          if(temp[i]==9){
            temp[i] = 0
          }else{
            temp[i] = Number(temp[i])+1;
          }
          res.push(temp.join(''))
        }
        return res
      }
      function down(str){
        var res = [];
        for(var i = 0;i<str.length;i++){
          var temp = str.split('')
          if(temp[i]==0){
            temp[i] = 9
          }else{
            temp[i] = Number(temp[i])-1;
          }
          res.push(temp.join(''))
        }
        return res
      }
      console.log(down('1100'))
      console.log(up('1100'))

      function lock(target,deadend){
        var q = [];
        var visited = [];
        q.push('0000');
        visited.push('0000')
        var count = 0;
        while(q.length>0){
          var len = q.length;
          for(var i = 0;i<len;i++){
            var cur = q.shift();
            // 判断
            if(cur==target){
              return count
            }
            if(deadend.includes(cur)){
              console.log('....');
              continue
            }
              var ups = up(cur);
              var downs = down(cur);
              for(var j = 0;j<ups.length;j++){
                if(!visited.includes(ups[j])){
                  q.push(ups[j])
                  visited.push(ups[j])
                }
              }
              for(var j = 0;j<downs.length;j++){
                if(!visited.includes(downs[j])){
                  q.push(downs[j])
                  visited.push(downs[j])
                }
              }
            
            console.log(visited);
              console.log(q);
            
            i--;
            len--;
          }
          count++
          console.log(count);
        }
        return count    
      }
      console.log(lock('0202',['0201','0101','0102','1212','2002']))
    </script>
  </body>
</html>
